Kruskal's Algorithm
The core of Kruskal's Algorithm is the Minimum Spanning Tree (MST), which connects all vertices in a graph with the least possible total edge weight without forming a cycle.
This technique is widely used in network design problems, such as in designing LAN or optical networks, where efficiency is key to minimizing the cost of connections.
Problem
Given a graph with a set of vertices and edges, the goal is to find a subset of edges that connects all vertices with the minimum total weight while avoiding any cycles.
Kruskal's Algorithm employs a greedy approach to achieve this.
Video Lecture
Input
A graph consisting of vertices and weighted edges.
Output
The minimum spanning tree of the graph, represented by the edges included in the MST.
Example:
- Edge 1 - (A, B), weight = 4
- Edge 2 - (B, C), weight = 2
- Edge 3 - (A, D), weight = 3
Steps of Kruskal's Algorithm
1. Sorting Edges by Weight
All edges in the graph are sorted in increasing order of their weights.
2. Adding Edges to the MST
Edges are added to the MST one by one in increasing order of weight. Only edges that don't form a cycle with already added edges are included.
3. Stopping Condition
The process stops when the number of edges in the MST equals the number of vertices minus one (|V| - 1).
Disjoint Set Data Structure
To keep track of which vertices are in the same connected component, a Disjoint Set (also known as Union-Find) data structure is used.
This data structure supports two main operations:
- Find: Determines the set to which a particular element belongs.
- Union: Merges two sets together.
By using Disjoint Set, Kruskal's Algorithm efficiently checks whether adding an edge would form a cycle.
Kruskal's Algorithm
Kruskal(G, E)
Input: A graph G with vertices and edges E, where each edge has a weight.
Output: A Minimum Spanning Tree (MST) of the graph, represented by a subset of edges.
Step 1: Start.
Step 2: Sort all edges in increasing order of their weight.
Step 3: Initialize an empty set MST to store the edges of the Minimum Spanning Tree.
Step 4: Initialize a Disjoint Set data structure to keep track of connected components of the vertices.
Step 5: For each edge (u, v) in the sorted list of edges:
Step 6: Use the Disjoint Set to check if vertices u and v are in different sets (i.e., they are not already connected).
Step 7: If they are in different sets, add the edge (u, v) to MST and perform the union operation to combine their sets.
Step 8: If they are in the same set, skip the edge to avoid forming a cycle.
Step 9: Continue checking the next edges in the sorted list.
Step 10: Stop when the MST contains exactly V-1 edges (where V is the number of vertices).
Step 11: Output the MST, which contains the edges of the Minimum Spanning Tree.
Step 12: Stop.
N Queens Problem using Backtracking code
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
#define INF 999999
typedef struct {
int u, v, w;
} Edge;
int parent[MAX], rank[MAX];
Edge edges[MAX];
int edgeCount = 0, vertexCount;
void initUnionFind() {
for (int i = 0; i < vertexCount; i++) {
parent[i] = i;
rank[i] = 0;
}
}
int find(int i) {
if (i != parent[i]) {
parent[i] = find(parent[i]);
}
return parent[i];
}
void unionSets(int x, int y) {
int xRoot = find(x);
int yRoot = find(y);
if (xRoot != yRoot) {
if (rank[xRoot] < rank[yRoot]) {
parent[xRoot] = yRoot;
} else if (rank[xRoot] > rank[yRoot]) {
parent[yRoot] = xRoot;
} else {
parent[yRoot] = xRoot;
rank[xRoot]++;
}
}
}
int compare(const void *a, const void *b) {
return ((Edge *)a)->w - ((Edge *)b)->w;
}
void kruskal() {
qsort(edges, edgeCount, sizeof(edges[0]), compare);
initUnionFind();
int mstWeight = 0;
printf("Edges in the Minimum Spanning Tree:\n");
for (int i = 0; i < edgeCount; i++) {
int u = edges[i].u;
int v = edges[i].v;
if (find(u) != find(v)) {
printf("%d -- %d (Weight: %d)\n", u, v, edges[i].w);
unionSets(u, v);
mstWeight += edges[i].w;
}
}
printf("Total Weight of MST: %d\n", mstWeight);
}
int main() {
int e;
printf("Enter number of vertices: ");
scanf("%d", &vertexCount);
printf("Enter number of edges: ");
scanf("%d", &e);
printf("Enter edges (u v w):\n");
for (int i = 0; i < e; i++) {
scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].w);
edgeCount++;
}
kruskal();
return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Edge {
int u, v, w;
};
class DisjointSet {
public:
vector<int> parent, rank;
DisjointSet(int n) {
parent.resize(n);
rank.resize(n, 0);
for (int i = 0; i < n; i++) parent[i] = i;
}
int find(int i) {
if (i != parent[i]) {
parent[i] = find(parent[i]);
}
return parent[i];
}
void unionSets(int x, int y) {
int xRoot = find(x);
int yRoot = find(y);
if (xRoot != yRoot) {
if (rank[xRoot] < rank[yRoot]) {
parent[xRoot] = yRoot;
} else if (rank[xRoot] > rank[yRoot]) {
parent[yRoot] = xRoot;
} else {
parent[yRoot] = xRoot;
rank[xRoot]++;
}
}
}
};
bool compareEdges(const Edge &a, const Edge &b) {
return a.w < b.w;
}
void kruskal(vector<Edge> &edges, int vertexCount) {
DisjointSet ds(vertexCount);
sort(edges.begin(), edges.end(), compareEdges);
int mstWeight = 0;
cout << "Edges in the Minimum Spanning Tree:\n";
for (const auto &edge : edges) {
int u = edge.u;
int v = edge.v;
if (ds.find(u) != ds.find(v)) {
cout << u << " -- " << v << " (Weight: " << edge.w << ")\n";
ds.unionSets(u, v);
mstWeight += edge.w;
}
}
cout << "Total Weight of MST: " << mstWeight << endl;
}
int main() {
int vertexCount, e;
cout << "Enter number of vertices: ";
cin >> vertexCount;
cout << "Enter number of edges: ";
cin >> e;
vector edges(e);
cout << "Enter edges (u v w):\n";
for (int i = 0; i < e; i++) {
cin >> edges[i].u >> edges[i].v >> edges[i].w;
}
kruskal(edges, vertexCount);
return 0;
}
import java.util.*;
class Edge {
int u, v, w;
Edge(int u, int v, int w) {
this.u = u;
this.v = v;
this.w = w;
}
}
class DisjointSet {
int[] parent, rank;
DisjointSet(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
}
int find(int i) {
if (i != parent[i]) {
parent[i] = find(parent[i]);
}
return parent[i];
}
void unionSets(int x, int y) {
int xRoot = find(x);
int yRoot = find(y);
if (xRoot != yRoot) {
if (rank[xRoot] < rank[yRoot]) {
parent[xRoot] = yRoot;
} else if (rank[xRoot] > rank[yRoot]) {
parent[yRoot] = xRoot;
} else {
parent[yRoot] = xRoot;
rank[xRoot]++;
}
}
}
}
public class Kruskal {
public static void kruskal(List<Edge> edges, int vertexCount) {
Collections.sort(edges, Comparator.comparingInt(e -> e.w));
DisjointSet ds = new DisjointSet(vertexCount);
int mstWeight = 0;
System.out.println("Edges in the Minimum Spanning Tree:");
for (Edge edge : edges) {
int u = edge.u;
int v = edge.v;
if (ds.find(u) != ds.find(v)) {
System.out.println(u + " -- " + v + " (Weight: " + edge.w + ")");
ds.unionSets(u, v);
mstWeight += edge.w;
}
}
System.out.println("Total Weight of MST: " + mstWeight);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter number of vertices: ");
int vertexCount = scanner.nextInt();
System.out.print("Enter number of edges: ");
int e = scanner.nextInt();
List<Edge> edges = new ArrayList<>();
System.out.println("Enter edges (u v w):");
for (int i = 0; i < e; i++) {
int u = scanner.nextInt();
int v = scanner.nextInt();
int w = scanner.nextInt();
edges.add(new Edge(u, v, w));
}
kruskal(edges, vertexCount);
scanner.close();
}
}
class DisjointSet:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, i):
if i != self.parent[i]:
self.parent[i] = self.find(self.parent[i])
return self.parent[i]
def union(self, x, y):
x_root = self.find(x)
y_root = self.find(y)
if x_root != y_root:
if self.rank[x_root] < self.rank[y_root]:
self.parent[x_root] = y_root
elif self.rank[x_root] > self.rank[y_root]:
self.parent[y_root] = x_root
else:
self.parent[y_root] = x_root
self.rank[x_root] += 1
def kruskal(vertex_count, edges):
edges.sort(key=lambda edge: edge[2]) # Sort edges by weight
ds = DisjointSet(vertex_count)
mst_weight = 0
mst_edges = []
print("Edges in the Minimum Spanning Tree:")
for u, v, w in edges:
if ds.find(u) != ds.find(v):
mst_edges.append((u, v, w))
print(f"{u} -- {v} (Weight: {w})")
ds.union(u, v)
mst_weight += w
print("Total Weight of MST:", mst_weight)
if __name__ == "__main__":
vertex_count = int(input("Enter number of vertices: "))
e = int(input("Enter number of edges: "))
edges = []
print("Enter edges (u v w):")
for _ in range(e):
u, v, w = map(int, input().split())
edges.append((u, v, w))
kruskal(vertex_count, edges)
Time Complexity of Kruskal's Algorithm
Time Complexity Basic Operations: Sorting Edges and Union-Find Operations
Analysis
The time complexity of Kruskal's Algorithm is determined by two primary operations: sorting the edges and performing the Union-Find operations.
1. Sorting the Edges: Sorting all the edges takes O(E log E) time, where E is the number of edges in the graph. This step is necessary to ensure that we can pick the smallest edges first.
2. Union-Find Operations: The Union-Find data structure is used to detect cycles while forming the Minimum Spanning Tree (MST). Each union or find operation can be performed in nearly constant time, O(log V), where V is the number of vertices, using techniques like path compression and union by rank.
Since we perform a Union-Find operation for each edge, the total time spent on Union-Find operations is O(E log V).
Overall Time Complexity: The overall time complexity of Kruskal's Algorithm is the sum of the time required for sorting the edges and the time for performing the Union-Find operations. Therefore, the total time complexity is:
T(E, V) = O(E log E) + O(E log V)
Since E can be at most V^2 in a dense graph, the time complexity can also be represented as O(E log V) for practical purposes, since log E is similar to log V.